- gives us a comparison range of
- 0x0100 1101 0111 0000 0000 0000 0000 0000 through
- 0x0100 1101 0111 0100 0000 0000 0000 0000
- or 1299185664 through 1299447808.

This simple restriction on the number of digits that needs to be searched reduces the potential population which requires a full comparison by a factor of 2⁵or one 32^nd. The actual reduction will depend entirely on the key-template generation algorithm's makeup. This makeup or implementation be controlled by the developers of the algorithm so it does not affect the accuracy ratings of the biometrics.

FIG. 2 illustrates the process of using the bioindex. After the reaw biometric data is captured foridentification21, the bioindex key or dynamic key and range of error are calculated or determined22 from the captured biometric data, in a manner as described above for enrollment. The algorithmic process described for steps23-26 can be accomplished in any number of ways as will be apparent to one of ordinary skill in these arts. For example, we could have pre-indexed the database and pull only that segment of relevance to the key for examination to insert intostep23. In any event, atstep23, we read the next template key stored in the database, and if it is within the range of error or matching the key generated instep22, we compare the biometric templated data at this key in the database to the biometric captured and templated in the database instep25. If the captured biometric matches the stored,step26, we have identified the subject by noting the ID information associated with the matched data record for an individual in our biometric data database.

InFIG. 3 we illustrate the general environment of the working of the preferred embodiments of the invention. Any number of individuals P0 . . . Pn may be enrolled at theenrollment facility31. The templates from this enrollment are transferred, usually as Binary Large Objects or BLOBs to adata storage server32 which holds the database. Given the shrinking size of memories, it is possible that the data servers and enrollment devices may be combined in the future. In any case, thedatabase32awill hold the BLOBs form the enrolled population. From each BLOB or template at least one key will be developed and stored in a related database oftemplate keys32k.

When a subject Ps is checked and biometric data is read from him or her at a biometric reader/collector system36, abiometric template35 is extracted therefrom. Preferably adynamic key34 is developed from that template, although a regular key could be generated. Aprocess33 like the process illustrated inFIG. 2 compares this key and eventually the template against the database, using the template keys to shrink the amount of comparisons that need to be done to find a match. Note that a user-id or subject ID should be associated with each template so that the user or subject person can be found when his biometric is matched and other data about the subject can be associated with the results of the search. Since this is why the invention is created generally, it is not seen useful to illustrate a separate data file or field for this name or other related data in the drawing.

We now describe an example method of creating a natural database record key using the ANSI/NIST ITL 1-2000 standard, using the Type-9 minutiae record, using fingerprints.

NIST Special Publication 500-245, “American National Standard for Information Systems—Data Format for the Interchange of Fingerprint, Facial, & Scar Mark & Tattoo (SMT) Information”, at page 10, describes Type 9 minutae records as follows: “Type-9 logical records shall contain, and be used to exchange geometric and topological minutiae and related information encoded from a finger or pal. Each record shall represent the processed image data from which the location and orientation descriptors of extracted minutiae characteristics are listed. The primary use of this record type shall be for remote searching of latent prints. Each Type-9 logical record shall contain the minutiae data read from a fingerprint, palm, or latent image”.

The fingerprint is laid out on a grid and the positions of any points of interest, such as where two ridges meet, are noted. The positions and types of these ‘minutiae’ are noted and stored in a file. SeeFIG. 4 for an illustration of such a fingerprint. The arrows point out the minutiae.

Once the fingerprint data is captured and processed it is a set of points on a grid. One such grid with points is shown inFIG. 5. Note that the data related to each point has an attribute, a pair of grid coordinates (from a 5,000 point grid) and an angle value in the parenthesis near each point. There may be many more such points in a fingerprint.

Thus, the data file describing a fingerprint becomes a collection of points that have type attributes (A,B,C,D), X-Y coordinates, and a theta value (the last number in the value), which indicates the angle of the ridge in degrees. When trying to locate a fingerprint file matching a sample fingerprint, a computer searches these point collections until it finds a record that matches the ones from the sample, i.e., the current search criteria. The problem is that this method of searching, while precise, is very slow. A way to narrow down the search field is needed.

What we do to organize the data is to divide the fingerprint grid into sections and average all the minutiae in that section into one ‘composite’ minutia data file. Creating a composite helps smooth out any deviations in the data, helping to avoid any false rejections.

There are several ways to average out the data, but for illustrative purposes we will average each datum separately and then concatenate into one string. We review theFIG. 6 illustration of a grid for this discussion. We average the letters by assigning them values (A=1, B=2, C=3, and D=4). (We average rounding up in this example (i.e., rounding C and D to get D), but any mathematical expedient can be used so long as it is consistent throughout the use of the invention). We will assign quadrants starting at the upper left hand and going clockwise. Averaging the three points in quadrant 1 gives us a composite value of B10132003067. There is only one point in quadrant 2, so the key now becomes B10132003067B10262005047. The final key becomes B10132003067B10262005047D10221997089A10131998234.

It is also possible to perform the key generation in successive stages. Rather than go directly from the NIST standard 5000×5000 grid to a 2×2 grid, it may be more accurate to go in stages, as illustrated. For the purposes of clarity, only the X and Y values are included, as illustrated inFIG. 7.

The original minutiae points are illustrated in as encircled. These points are pulled down to the nearest 5, that is, it's nearest lower right hand corner of its local five-by-five grid. If more than one point is contained in any 5×5 grid, the points are combined into a single point, illustrated as a point in a square. The local composites are then averaged into the quadrant composites, illustrated as a point in a triangle. These quadrant composites may then be used to generate the key field or fields to be used.

Going through the process in stages will help avoid false rejects because of minor deviations in the minutiae from different images of the same finger.

An alternate strategy to creating a key is to create a key using several fields in the record. Instead of generating one long string, we can take each composite minutia that was generated and bring it out into a separate record field, and then use the several fields as a composite search key.

This process will generate a NON-UNIQUE key. I have avoided calling the generated key a ‘primary key’ as the term is used in database terminology, because a primary key by definition, is unique. This method will not always generate a unique key, even if we use several fields. What it will do is enable a non-unique index to be created, which will speed up the initial search stage by a factor of thousands.

Once a small group of near matches has been identified, the fingerprint search software can then search the small group for the unique print in the normal fashion.

SUMMARY

We have described a system for quickly finding a match for a large number in a set of large numbers without having to compare each digit of each large number to the one we are trying to match. We have applied this system to biometric data matching describing a system and method to accomplish this. We have described it in detail with respect to a particular biometric, that is, fingerprint data.

Claims

1. A method for increasing the rapidity of biometric authentication of a subject against large population samples, comprising:

enrolling a plurality of subjects by capturing raw biometric data from each subject via at least one biometric data capturing device during an enrollment process;

generating, for each enrolled subject, an enrollment biometric template from the raw biometric data, the enrollment biometric template comprising a plurality of points of interest;

storing each said enrollment biometric template in association with a subject identification ID, the subject identification ID identifying a particular one of the subjects in the plurality of subjects;

generating a biometric template key from the biometric template, the biometric template key being generated by splitting the biometric template into a plurality of regions, the template key comprising a concatenation of the averages of the points of interest within each region;

storing the generated biometric template key in association with the subject identification ID with which the enrollment biometric template is associated;

generating an authentication template from raw biometric data of an unknown subject captured during an authentication process, the authentication template comprising a plurality of points of interest;

generating an authentication key from the authentication template, the authentication key being generated by splitting the authentication template into a plurality of regions, the authentication key comprising a concatenation of the averages of the points of interest within each region;

searching the stored biometric template keys to identify a set of biometric template keys matching the authentication key;

retrieving the enrollment biometric templates associated with each biometric template key in the set of identified biometric keys matching the authentication key; and,

comparing the authentication template against the retrieved enrollment biometric templates and authenticating the unknown subject if the authentication template matches one of the retrieved enrollment biometric templates.

2. The method ofclaim 1, the authentication template being a dynamic template, and the authentication key being a dynamic key.

3. The method ofclaim 1, the plurality of regions into which the biometric template and the authentication template are divided comprising quadrants.

4. The method ofclaim 1, the raw biometric data comprising fingerprint data.

5. The method ofclaim 1, the plurality of regions comprising a grid.

6. The method ofclaim 5, wherein said grid uses the ANSI/NIST ITL 1-2000 standard.

7. The method ofclaim 5, the template generation processes further comprising organizing the respective grids of data points in a set manner to produce uniform data files for each biometric capture process.

8. (canceled)

9. The method ofclaim 1, searching the stored biometric template keys to identify a set of biometric template keys matching the authentication key comprising matching significant bits of the biometric template keys with significant bits of the authentication key.

10. The method ofclaim 9, wherein the bits matched staff from most significant bit and continue in sequence to the least significant bit.

11. The method ofclaim 10, wherein the number of bits matched corresponds to a pre-determined error level.

12. The method ofclaim 11, wherein the pre-determined error level is used to return a range of biometric template keys to compensate for biometric collection error.

13. (canceled)

14. A method for quickly determining a match between an unknown subject biometric and a database of enrolled subject biometric files, each biometric file stored in the database having associated therewith a biometric template generated from each biometric file, a biometric key associated with and derived from the biometric template, and an a subject ID field, the biometric key being generated by splitting the biometric template into a plurality of regions, the biometric key comprising a concatenation of the averages of the points of interest within each region, the method comprising:

generating an authentication template from biometric data of an unknown subject captured during an authentication process;

identifying a set of matching biometric templates by comparing the authentication key against the biometric keys stored in the database;

retrieving biometric templates associated with the biometric keys in the set of matching biometric templates;

comparing the authentication template to the retrieved biometric templates; and,

if the authentication template matches a retrieved biometric template, authenticating the unknown subject as the subject ID associated with the biometric template.

15. The method ofclaim 14 wherein said authentication template is dynamic, and wherein said authentication key is dynamic.

16. The method ofclaim 14, wherein the captured biometric data comprises a plurality of points of interest.

17. The method ofclaim 14 wherein the authentication and enrollment processes employ fingerprint data as raw biometric data.

18. The method ofclaim 14, the regions being organized to form a grid.

19. The method ofclaim 18, wherein said grid uses the ANSI/NIST ITL 1-2000 standard.

20. The method ofclaim 18 wherein said template generation process organizes said grid of data points in a set manner to produce uniform data files for each biometric capture process.

21. The method ofclaim 14, the plurality of regions into which the biometric template and the authentication template are divided comprising quadrants.

22. The method ofclaim 14, searching the stored biometric template keys to identify a set of biometric template keys matching the authentication key comprising matching significant bits of the biometric template keys with significant bits of the authentication key.

23. The method ofclaim 22, wherein the bits matched staff from most significant bit and continue in sequence to the least significant bit.

24. The method ofclaim 23, wherein the number of bits matched corresponds to a pre-determined error level.

25. The method ofclaim 24, the pre-determined error level being used to return a range of biometric template keys to compensate for biometric collection error.

26. (canceled)

27. An apparatus for quickly determining a match between an unknown subject's biometric and a set of subject biometric files in a database of enrolled subject biometric files comprising:

a database of enrolled subject biometric files, each biometric file stored in the database having associated therewith a biometric template generated from each biometric data file, a biometric key associated with and derived from the biometric template, and a subject ID field the biometric key being generated by splitting the biometric template into a plurality of regions, the biometric key comprising a concatenation of the averages of the points of interest within each region;

a biometric sensing device for capturing biometric data from the unknown subject;

computing means for generating an authentication template data record based on the captured biometric data, the authentication template data record comprising a plurality of points of interest within the biometric data;

computing means for determining an authentication key from said template data record, the authentication key being generated by splitting the template data record into a plurality of regions, the authentication key comprising a concatenation of the averages of the points of interest within each region;

computing means for finding those biometric keys stored in the database which are within a range of values around the authentication key; and

comparison means for comparing the authentication template against the biometric templates associated with the found biometric keys.