Bioindex mechanism for increasing the relative speed of biometric identification against large population samples
View Patent ↗A method and system for determining a smaller sample of large data objects to search through for a match to one under test. The data objects are in preferred embodiments biometric templates.
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 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 of claim 1 , the authentication template being a dynamic template, and the authentication key being a dynamic key.
3. The method of claim 1 , the plurality of regions into which the biometric template and the authentication template are divided comprising quadrants.
4. The method of claim 1 , the raw biometric data comprising fingerprint data.
5. The method of claim 1 , the plurality of regions comprising a grid.
6. The method of claim 5 , wherein said grid uses the ANSI/NIST ITL 1-2000 standard.
7. The method of claim 5 , the terminal 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. The method of claim 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.
9. The method of claim 8 , wherein the bits matched start from most significant bit and continue in sequence to the least significant bit.
10. The method of claim 9 , wherein the number of bits matched corresponds to a pre-determined error level.
11. The method of claim 10 , wherein the pre-determined error level is used to return a range of biometric template keys to compensate for biometric collection error.
12. 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 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;
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;
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.
13. The method of claim 12 wherein said authentication template is dynamic, and wherein said authentication key is dynamic.
14. The method of claim 12 , wherein the captured biometric data comprises a plurality of points of interest.
15. The method of claim 12 wherein the authentication and enrollment processes employ fingerprint data as raw biometric data.
16. The method of claim 12 , the regions being organized to form a grid.
17. The method of claim 16 , wherein said grid uses the ANSI/NIST ITL 1-2000 standard.
18. The method of claim 16 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.
19. The method of claim 12 , the plurality of regions into which the biometric template and the authentication template are divided comprising quadrants.
20. The method of claim 12 , 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.
21. The method of claim 20 , wherein the bits matched start from most significant bit and continue in sequence to the least significant bit.
22. The method of claim 21 , wherein the number of bits matched corresponds to a pre-determined error level.
23. The method of claim 22 , the pre-determined error level being used to return a range of biometric template keys to compensate for biometric collection error.
24. 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.