Method of fast fingerprint search space partitioning and prescreening
View Patent ↗A method of fast fingerprint search space partitioning and prescreening is disclosed. The method comprises the steps of: inputting the contents of a fingerprint repository comprising file fingerprints for index creation; creating an index based on each minutia and selected neighbors of each minutia in each file fingerprint in the repository; searching the index to identify all minutiae which correspond to the minutiae in a search fingerprint; and analyzing results of this search to determine which file fingerprints contributed the most minutiae with the best correspondence to the minutiae in the search fingerprint.
1. A method of fast fingerprint search space partitioning and prescreening, said method comprising the steps of:
inputting the contents of a fingerprint repository comprising file fingerprints for index creation;
creating an index based on each minutia and selected neighbors of each minutia in each file fingerprint in the repository;
searching the index to identify all minutiae which correspond to the minutiae in a search fingerprint; and
analyzing results of this search to determine which file fingerprints contributed the most minutiae with the best correspondence to the minutiae in the search fingerprint,
wherein each file fingerprint of the fingerprint repository includes the following data: the number of minutiae in the fingerprint; and for each minutia: the base angle of the minutia in a frame of reference whose angular orientation to and permissible deviation from the axis of the finger of the fingerprint is pre-defined; the Cartesian coordinates (X, Y) of the minutia relative to the same frame of reference; the minutia index of the nearest neighboring minutia in each of eight octants wherein each octant comprises a 45 degree wedge and the first octant of which is centered on the base angle of the minutia and wherein the nearest neighboring minutia are know as octant neighbors; a count of friction ridges between the minutia and each of its eight octant neighbors; an Euclidean distance between the minutia and each of its eight octant neighbors and the difference between the base angle of the minutia and the base angle of each of its eight octant neighbors.
2. A method according to claim 1 , wherein the index created from the repository of file fingerprints comprises the following information: 1) an index of each subject in the repository; 2) an index of each finger of each subject; and 3) an index of the minutia for each finger of each subject in the repository.
3. A method according to claim 1 , wherein if an index already exists, subjects of the repository are compared with subjects of the existing index to determine whether a subject of the repository is already in the index to prevent duplication of subjects in the index.
4. A method according to claim 1 , wherein the step of creating the index includes creating neighbor combinations for each finger of each subject of the repository wherein a neighborhood combination is based on selecting 2 of eight octant neighbors to produce 28 possible combinations per finger.
5. A method according to claim 4 , wherein the step of creating the index further includes the step of creating a hash table file for each finger-neighbor combination.
6. A method according to claim 5 , wherein the hash table file includes the following information: an index of a hash list node in the hash list file and the number of hash list nodes associated with a hash code.
7. A method according to claim 6 , wherein the hash code is at least a 15-bit hash code.
8. A method according to claim 4 , wherein the step of creating the index further includes the step of creating a hash list file for each finger-neighbor combination wherein a hash list comprises N hash list nodes, where N is a function of the number of minutiae in the repository, plus any room needed for repository expansion.
9. A method according to claim 8 , wherein each hash list node contains the following data: a hash code to identify the hash list file, the number of populated repository index slots in the hash list file and a plurality of repository index slots.
10. A method according to claim 9 , wherein the optimum number of slots in a node is a function of the hash code distribution which is a function of the fingerprint characteristics in the repository.
11. A method according to claim 4 , wherein the step of creating the index further includes creating one hash list node used file for each finger-neighbor combination wherein a hash list node used file is a bookkeeping device which tracks which hash list nodes in the file are populated at any given time.
12. A method according to claim 4 , wherein each neighbor combination of each minutia of each finger of each subject of the repository which is not already in the index is added into the index.
13. A method according to claim 1 , wherein the step of searching the index comprises the steps of identifying all subjects that contain minutiae and neighbor combinations similar to minutiae and neighbor combinations of the search fingerprint and creating a list of candidate subjects.
14. A method according to claim 13 , wherein, when all of the minutiae and neighbor combinations have been processed, the step of analyzing the search results comprises scoring and ranking each of the candidate subjects.
15. A method according to claim 14 , wherein the step of analyzing the search results further include generating a list of the most likely matches from all of the candidate subjects of the list.
16. A method according to claim 13 , wherein the following data for each finger is used for the search: 1) the number of times a given finger is visited during the search; 2) the number of individual minutiae that participate in a match; 3) the degree to similarity between the orientation of the minutia of the search fingerprint and a file fingerprint; and 4) a score which is proportional to the degree of match between the search fingerprint and the file fingerprint.
17. A method according to claim 16 , wherein after the data is collected during the search, the step of analyzing the search comprises formulating a raw score according to the following equation: Raw Score=(VisitCount−MinutiaCount)*(max(degree of similarity between the orientation of the minutia of the search fingerprint and the file fingerprint)).
18. A method according to claim 17 , wherein the raw score for each finger of each candidate subject is normalized using statistical techniques appropriate for the observed exponential distribution of the raw scores.
19. A method according to claim 18 wherein the standard deviation of the entire set of scores for the finger is calculated and the each raw score is then divided by the standard deviation to produce a normalized exponential score for the Subject/Finger and the normalized exponential scores for each finger of each candidate mate are combined to produce a multi-finger score by summation.
20. A method according to claim 19 , wherein candidate mates are scanned from first to last and if the multi-finger score for a particular candidate mate exceeds a pre-determined threshold, that subject is appended to the result list.
21. A method according to claim 20 , wherein the list is sorted in descending multi-finger-score order to create a list of candidate mate subjects ordered from most likely (highest score) through least likely (lowest score).